//
// Created by Incredible on 17/3/23.
//

#ifndef GRAPHTHEORY_COMPONENT_H
#define GRAPHTHEORY_COMPONENT_H

#include <iostream>

using namespace std;

/**
 * 连通分量
 *
 * 连接性求解：在同一连通分量上的顶点都是连通的，他们拥有相同的id
 */

template<typename Graph>
class Componment {

    Graph graph;        //待求图
    bool *visited;      //访问标志数组
    int *id;            //集合id（所属连通分量）
    int ccount;         //联通分量

    //深度优先遍历
    void dfs(int i) {

        visited[i] = true;
        id[i] = ccount;

        //TODO 无typename报错,添加保证编译器明确Graph的类型
        typename Graph::adjIterator adjIterator(graph, i);
        //继续遍历顶点的临接点，利用iterator遍历邻接点

        for (int i = adjIterator.begin(); !adjIterator.end(); i = adjIterator.next()) {

            //该节点没有被访问，则递归进入访问
            if (!visited[i]) {
                dfs(i);
            }
        }
    }

public:

    //初始化  参数： 待求图
    Componment(Graph graph) : graph(graph) {
        visited = new bool[graph.V()];     //访问状态数组
        id = new int[graph.V()];
        ccount = 0;     //初始态无连通分量

        //初始化visited数组
        for (int j = 0; j < graph.V(); ++j) {
            visited[j] = false;
        }

        //初始化id数组
        for (int i = 0; i < graph.V(); i++) {
            id[i] = 0;
        }

        for (int i = 0; i < graph.V(); ++i) {

            //该节点未被访问
            if (!visited[i]) {
                //对该顶点进行DFS
                dfs(i);
                ccount++;
            }
        }
    }

    //返回连通分量
    int count() {
        return ccount;
    }

    //是否连通
    bool isConnection(int a, int b){
        return id[a] == id[b];
    }

};

#endif //GRAPHTHEORY_COMPONENT_H
